class Heapq:
    """
        生成大根堆
    """

    def __HeapAdjust(self, nums: list, start: int, end: int) -> None:
        """
            筛选法调整堆：
            堆是以列表进行表示的, 假设 [start + 1, end] 已经是堆了，要把[start, end] 变为堆
        """
        i = start
        # 记录一下堆顶元素（这是要调整到堆里的元素）
        rc = nums[i]
        # 判断不能超过堆长度（也就是此刻数组的长度）
        while i * 2 + 1 <= end:
            # 左子节点
            j = i * 2 + 1
            # 判断左右子节点哪个大, nums[j] < end 说明存在右子节点
            if j < end and nums[j] < nums[j + 1]: j += 1
            # 将 rc 与 最大的子节点比较, 如果大于等于当前子节点，说明该插入到这
            if rc >= nums[j]: break
            # 否则，子节点上移
            nums[i] = nums[j]
            i = j
        
        # 最后不管是找到插入位置，还是执行到最后到了叶子结点，都是插入位置
        nums[i] = rc

    
    def __heapify(self, nums: list) -> None:
        """
            将数组变为堆， 由完全二叉树的性质可知，（下标从1开始）所有下标大于 n // 2 的节点都是叶子结点，
            而 叶子结点都是以自己为 根的堆。 我们只需要 将 前 0 - n // 2的 节点进行 调整堆，就可以把整个列表调整为堆
        """
        n = len(nums)
        for i in range((n + 1) // 2 - 1, -1, -1):
            # 调用调整堆函数
            self.__HeapAdjust(nums, i ,n - 1)
    
    
    def __pop(self, nums: list) -> int:
        """
            删除堆中最大的元素，堆顶元素
        """
        n = len(nums)
        nums[0], nums[-1] = nums[-1], nums[0]
        # 得到最大值，堆顶元素，然后调整堆
        rst = nums.pop()
        # 元素大于0时才能执行调整堆
        if len(nums) > 0:
            self.__HeapAdjust(nums, 0 ,n - 2)

        return rst


    def __push(self, nums: list, num: int):
        """
            向堆中添加元素， 因为是列表，默认尾部添加
        """
        nums.append(num)
        # 此时 num 为叶子节点，应该由下到上找到他该插入的位置
        n = len(nums)
        i = n - 1
        # 寻找位置不能超过列表上限（堆顶）
        while (i - 1) // 2 >= 0:    
            """
                这里说明一下，因为以 0 为开始节点的情况下， 根 左右三者关系是 i i * 2 + 1   i * 2 + 2
                无法从叶子结点 // 2 得到根节点。  但是以 1为开始的就可以。 i  i*2, i * 2 + 1  
            """
            cur_root = (i - 1) // 2
            # 小于当前根节点，那就插入到当前位置
            if nums[cur_root] > num: break
            nums[i] = nums[cur_root]
            i = cur_root

        # 最后到了，为根位置了，或者找到插入位置，都执行插入
        nums[i] = num
    

    # 对外提供的接口
    def heapify(self, nums: list) -> None:
        """
            把数组调整为大根堆
        """
        self.__heapify(nums)
    

    def heappop(self, nums: list) -> int:
        """
            删除堆顶元素并返回
        """
        return self.__pop(nums)


    def heappush(self, nums: list, num: list) -> None:
        """
            向堆内添加元素
        """
        self.__push(nums, num)

    
    def heapSort(self, nums: list) -> None:
        """
            :param      nums: int
            将普通数组通过堆排序并返回, 原地排序，不适用额外数组
        """
        n = len(nums)
        # 先建堆
        self.__heapify(nums)
        # 再进行堆排序
        for i in range(n-1, 0, -1):
            # 将堆顶元素交换到堆尾，再进行调整堆
            nums[0], nums[i] = nums[i], nums[0]
            # 调整堆，将 [0, i - 1] 调整为堆
            self.__HeapAdjust(nums, 0, i - 1)

    def heapSort1(self, nums: list) -> None:
        """
            :param      nums: int
            将普通数组通过堆排序并返回, 原地排序，不适用额外数组
        """
        n = len(nums)
        # 先建堆
        self.__heapify(nums)
        # 再进行堆排序
        sortL = list()
        for i in range(n):
            rst = self.heappop(nums)
            sortL.append(rst)
        
        return sortL


# 开始测试

nums = [49, 38, 65, 97, 76, 13, 27, 49]
nums = [79, 56, 72, 38, 19, 52, 53, 23]
heap = Heapq()
# 1. 创建堆，并进行堆排序
# heap.heapSort(nums)
# heap.heapify(nums)

# 2. 测试pop()
# rst = heap.heappop(nums)

# 3. 测试 push()
heapList = []
for num in nums:
    heap.heappush(heapList, num)

# 此时heapList已经是堆了
print(heapList)
rst = heap.heapSort1(heapList)

print(heapList)
print(rst)

"""
heapList    [97, 76, 49, 49, 65, 13, 27, 38]
下标         0   1   2    3  4   5   6    7

                        97
                    76         49
                49     65   13    27 
            38

"""


"""
原始堆为：

             79 
        56        72
    38      19  52  53
  23


push 100 以后应该为

            100 
        79       72
    56     19  52   53
  23  38


而不是这种（出自一道选择题）
            100
        79       72
    56     19  52  53
38      23 

"""




